package com.ahpu.lyf.binarytree;

public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr={1,2,3,4,5,6,7};
        ArrBinaryTree arrBinaryTree=new ArrBinaryTree(arr);
        System.out.println("顺序存储二叉树的前缀遍历~~~");
        arrBinaryTree.preOrder();
        System.out.println("顺序存储二叉树的中缀遍历~~~");
        arrBinaryTree.infixOrder();
        System.out.println("顺序存储二叉树的后缀遍历~~~");
        arrBinaryTree.suffixOrder();
    }
}

/**
 * 顺序存储二叉树的特点:
 * 1)顺序二叉树通常只考虑完全二叉树
 * 2)第n个元素的左子节点为2 * n + 1
 * 3)第n个元素的右子节点为2 * n + 2
 * 4)第n个元素的父节点为(n-1)/2
 */
class ArrBinaryTree{
    private final int[] arr;

    public ArrBinaryTree(int[] arr){
        this.arr=arr;
    }

    public void preOrder(){
        this.preOrder(0);
    }

    public void infixOrder(){
        this.infixOrder(0);
    }

    public void suffixOrder(){
        this.suffixOrder(0);
    }

    /**
     * 顺序存储二叉树的前缀遍历
     * @param index 从0根节点开始遍历
     */
    private void preOrder(int index){
        if (arr==null||arr.length==0){
            System.out.println("数组为空，不能按照二叉树的前序遍历");
            return;
        }
        //输出这个元素
        System.out.println(arr[index]);
        //向左递归遍历
        if ((2*index+1)<arr.length){
            preOrder(2*index+1);
        }
        //向右递归遍历
        if ((2*index+2)<arr.length){
            preOrder(2*index+2);
        }
    }

    private void infixOrder(int index){
        if (arr==null||arr.length==0){
            System.out.println("数组为空，不能按照二叉树的中缀遍历");
            return;
        }
        //向左子节点遍历
        if ((2*index+1)<arr.length)
            infixOrder(2*index+1);

        //输出这个节点值
        System.out.println(arr[index]);

        //向右子节点遍历
        if ((2*index+2)<arr.length)
            infixOrder(2*index+2);
    }

    private void suffixOrder(int index){
        if (arr==null||arr.length==0){
            System.out.println("数组为空，不能按照二叉树的后缀遍历");
            return;
        }
        //向左子节点递归遍历
        if ((2*index+1)<arr.length)
            suffixOrder(2*index+1);
        //向右子节点递归遍历
        if ((2*index+2)<arr.length)
            suffixOrder(2*index+2);

        //输出这个节点值
        System.out.println(arr[index]);
    }
}
